/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 07 - 02
 * Time: 12:29
 */
import java.util.ArrayList;
import java.util.List;
    class BinaryTree {
        static class TreeNode {
            public char val;
            public TreeNode left;//左孩子的引用
            public TreeNode right;//右孩子的引用
            public TreeNode(char val) {
                this.val = val;
            }
        }

        //创建一棵二叉树,返回这棵树的根节点
        public TreeNode createTree() {
            TreeNode A = new TreeNode('A');
            TreeNode B = new TreeNode('B');
            TreeNode C = new TreeNode('C');
            TreeNode D = new TreeNode('D');
            TreeNode E = new TreeNode('E');
            TreeNode F = new TreeNode('F');
            TreeNode G = new TreeNode('G');
            TreeNode H = new TreeNode('H');
            A.left = B;
            A.right = C;
            B.left = D;
            B.right = E;
            C.left = F;
            C.right = G;
            E.right = H;
            return A;
        }

        //前序遍历1
        public void preOrder(TreeNode root) {
            if (root == null) {
                return;
            }
            System.out.print(root.val + " ");
            preOrder(root.left);
            preOrder(root.right);
        }
        //前序遍历2
        public List<Character> preorderTraversal(TreeNode root) {//如果<>里是TreeNode，则下面是list.add(root)
            List<Character> list = new ArrayList<>();//向上转型，每递归一次就创建一个List<Character>类型的变量list
            if (root == null) {
                return list;
            }
            list.add(root.val);
            List<Character> leftTree = preorderTraversal(root.left);
            list.addAll(leftTree);
            List<Character> rightTree = preorderTraversal(root.right);
            list.addAll(rightTree);
            return list;
        }

        //中序遍历1
        void inOrder(TreeNode root) {
            if (root == null) {
                return;
            }
            inOrder(root.left);
            System.out.print(root.val + " ");
            inOrder(root.right);
        }
        //中序遍历2
        public List<Character> inorderTraversal(TreeNode root) {
            List<Character> list = new ArrayList<>();
            if (root == null) {
                return list;
            }
            List<Character> leftTree = inorderTraversal(root.left);
            list.addAll(leftTree);
            list.add(root.val);
            List<Character> rightTree = inorderTraversal(root.right);
            list.addAll(rightTree);
            return list;
        }

        //后序遍历1
        void postOrder(TreeNode root) {
            if (root == null) {
                return;
            }
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.val + " ");
        }
        //后序遍历2
        public List<Character> postorderTraversal(TreeNode root) {
            List<Character> list = new ArrayList<>();
            if (root == null) {
                return list;
            }
            List<Character> leftTree = postorderTraversal(root.left);
            list.addAll(leftTree);
            List<Character> rightTree = postorderTraversal(root.right);
            list.addAll(rightTree);
            list.add(root.val);
            return list;
        }

        public static int nodeSize;
        //获取树中节点的个数：遍历思路
        void size(TreeNode root) {//返回值为void
            if (root == null) {
                return;
            }
            nodeSize++;
            size(root.left);
            size(root.right);
        }
        //获取树中节点的个数：子问题思路
        int size2(TreeNode root) {//返回值为int
            if (root == null) {
                return 0;
            }
            return size2(root.left) + size2(root.right) + 1;
        }

        public static int leafSize = 0;
        //获取叶子节点的个数：遍历思路
        void getLeafNodeCount1(TreeNode root) {
            if (root == null) {
                return;
            }
            if (root.left == null && root.right == null) {
                leafSize++;
            }
            getLeafNodeCount1(root.left);
            getLeafNodeCount1(root.right);
        }
        //获取叶子节点的个数：子问题思路
        int getLeafNodeCount2(TreeNode root) {
            if (root == null) {
                return 0;
            }
            if (root.left == null && root.right == null) {
                return 1;
            }
            return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
        }

        //获取第K层节点的个数
        int getKLevelNodeCount(TreeNode root, int k) {//root这棵树第k层节点数量=root.left这棵树第k-1层节点数量+root.right这棵树第k-1层节点数量
            if (root == null) {
                return 0;
            }
            if (k == 1) {//root不为null且k为1时，相当于属于第k层的一个节点数
                return 1;
            }
            return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1);
        }

        //获取二叉树的高度，时间复杂度：O(N)
        int getHeight(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int leftTreeHeight = getHeight(root.left);
            int rightTreeHeight = getHeight(root.right);
            return leftTreeHeight > rightTreeHeight ? leftTreeHeight + 1 : rightTreeHeight + 1;
        }

        // 检测值为value的元素是否存在
        TreeNode find(TreeNode root, char val) {

            return null;
        }

        //层序遍历
        void levelOrder(TreeNode root) {

        }

        // 判断一棵树是不是完全二叉树
        boolean isCompleteTree(TreeNode root) {
            return true;
        }
    }

